package newcoder_exp.justPractise;
 import java.util.*;

import org.junit.Test;
public class NC128 {
    class Solution {
        /**
         * max water
         * @param arr int整型一维数组 the array
         * @return long长整型
         * 找到左右来两边最近的两个大于当前位置的数，其较小者
         * 就是当前位置所能盛放
         */
        public long maxWater (int[] arr) {
            int len;
            if (arr == null || (len = arr.length)  <= 2)
                return 0;
            Stack<Integer> left = new Stack<>();
            Stack<Integer> right = new Stack<>();

            int[][] help = new int[len][2];
            for (int i = 0; i < len; i++) {
                while (!left.isEmpty() && arr[left.peek()] <= arr[i]) {
                    left.pop();
                }
                help[i][0] = left.isEmpty() ? -1 : left.peek();
               if (left.isEmpty())
                left.push(i);
            }


            for (int i = len - 1; i >= 0; i--) {
                while (!right.isEmpty() && arr[right.peek()] <= arr[i]) {
                    right.pop();
                }
                help[i][1] = right.isEmpty() ? -1 : right.peek();
                if (right.isEmpty())
                right.push(i);
            }

            int sum = 0;
            for (int i = 1; i < len - 1; i++) {
                int l = help[i][0], r = help[i][1];
                if (l < 0 || r < 0) {
                    continue;
                } else {
                    int h = Math.min(arr[l], arr[r]) - arr[i];
                    sum += h;
                }
            }
            return sum;
        }
    } 

    @Test
    public void test() {
        int[] nums = {3,1,2,5,2,4};
        Solution s = new Solution();
        long res = s.maxWater(nums);
        System.out.println(res);
    }
}
